package alo.p9;

import org.junit.Test;

import java.util.ArrayList;
import java.util.List;

public class Floyd {
    private int[][] matrix;

    private int[][] path;

    @Test
    public void test() {

        initMatrixAndPath(
                new int[][]{
                        {0, 1, 8, 5},
                        {1, 0, 7, 6},
                        {8, 7, 0, 2},
                        {5, 6, 2, 0}}
        );

        floyd(matrix, path);
        printShortDistance();
    }

    private void initMatrixAndPath(int[][] matrix) {
        this.matrix = matrix;
        this.path = new int[matrix.length][matrix.length];

        for (int i = 0; i < matrix.length; i++) {
            for (int j = 0; j < matrix[i].length; j++) {
                path[i][j] = j;
            }
        }
    }

    /**
     * 初始化邻接矩阵和path矩阵
     * @param matrix 邻接矩阵
     * @param path path矩阵
     */
    private void floyd(int[][] matrix, int[][] path) {
        for (int k = 0; k < matrix.length; k++) {
            for (int i = 0; i < matrix.length; i++) {
                for (int j = 0; j < matrix.length; j++) {
                    if (matrix[i][j] > matrix[i][k] + matrix[k][j]) {
                        matrix[i][j] = matrix[i][k] + matrix[k][j];
                        path[i][j] = path[i][k];
                    }
                }
            }
        }
    }

    /**
     * 打印路径
     */
    private void printShortDistanceDetail(int i, int j) {
        List<Integer> list = new ArrayList<>();
        list.add(j);
        int x = j;
        while (path[i][j] != x) {
            x = path[i][x];
            list.add(path[i][x]);
        }
        list.add(i);
        System.out.print("最短路径[v" + i + ",v" + j + "]为:");
        for (int k = list.size() - 1; k >= 0; k--) {
            System.out.print(list.get(k) + " ");
        }
        System.out.println();
    }

    /**
     * 打印路径和
     */
    private void printShortDistance() {
        for (int i = 0; i < matrix.length; i++) {
            for (int j = 0; j < matrix[i].length; j++) {
                System.out.println("v" + i + "到" + "v" + j + "最短路径为:" + matrix[i][j]);
                printShortDistanceDetail(i, j);
            }
        }
    }
}

